package com.leetcode.code;

/**
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 * <p>
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 * 说明:
 * <p>
 * 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
 */
public class LeetCode0215Java {
    public static void main(String[] args) {
        Solution solution = new Solution();

        System.out.println("结果：" + solution.findKthLargest(new int[] { 3, 2, 1, 5, 6, 4 }, 2));
    }

    private static class Solution {
        // 方法一 双轴快排
        //    public int findKthLargest(int[] nums, int k) {
        //        final int N = nums.length;
        //        Arrays.sort(nums);
        //        return nums[N - k];
        //    }

        // 方法二 快排 https://blog.csdn.net/shujuelin/article/details/82423852
        public int findKthLargest(int[] nums, int k) {
            final int N = nums.length;

            quickSort(nums, 0, nums.length - 1);
            return nums[N - k];
        }

        private void quickSort(int[] values, int leftIndex, int rightIndex) {
            if (leftIndex >= rightIndex) return;

            int pivotIndex = partitioning(values, leftIndex, rightIndex);
            quickSort(values, leftIndex, pivotIndex - 1);
            quickSort(values, pivotIndex + 1, rightIndex);
        }

        // 取基准值
        private int partitioning(int[] values, int leftIndex, int rightIndex) {
            int pivot = values[leftIndex];
            int pivotIndex = leftIndex;

            while (leftIndex < rightIndex) {
                while (values[rightIndex] >= pivot && rightIndex > leftIndex) {
                    rightIndex--;
                }

                while (values[leftIndex] <= pivot && rightIndex > leftIndex) {
                    leftIndex++;
                }

                if (leftIndex != rightIndex) swapValue(values, leftIndex, rightIndex);
            }

            values[pivotIndex] = values[leftIndex];
            values[leftIndex] = pivot;

            return leftIndex;
        }

        private void swapValue(int[] values, int leftIndex, int rightIndex) {
            int temp = values[leftIndex];
            values[leftIndex] = values[rightIndex];
            values[rightIndex] = temp;
        }

        // 快速选择 TODO
    }
}
